//https://leetcode.cn/problems/intersection-of-two-linked-lists/

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {

    struct ListNode* tailA, * tailB;
    tailA = headA;
    tailB = headB;
    int lenA = 1;
    int lenB = 1;

    //计算链表的长度
    while (tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }

    while (tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }

    //走到尾，判断是否有交点
    if (tailA != tailB)
        return NULL;

    int gap = abs(lenA - lenB);
    struct ListNode* longListNode = headA;
    struct ListNode* shortListNode = headB;
    if (lenA < lenB)
    {
        longListNode = headB;
        shortListNode = headA;
    }

    //长的链表先走差距步
    while (gap--)
    {
        longListNode = longListNode->next;
    }

    //一起走，直到找到交点
    while (longListNode != shortListNode)
    {
        longListNode = longListNode->next;
        shortListNode = shortListNode->next;
    }

    return longListNode;

}